import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvSource;

import java.util.Arrays;

/**
 * 排列序列
 * 题目：给出集合[1,2,3,...,n]，其所有元素共有n! 种排列。
 * 按大小顺序列出所有排列情况，并一一标记，当n = 3 时, 所有排列如下：
 * <p>
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * <p>
 * 给定n和k，返回第k个排列。
 * <p>
 * 示例 1：
 * 输入：n = 3, k = 3
 * 输出："213"
 * <p>
 * 示例 2：
 * 输入：n = 4, k = 9
 * 输出："2314"
 * <p>
 * 示例 3：
 * 输入：n = 3, k = 1
 * 输出："123"
 * <p>
 * 提示：
 * 1 <= n <= 9
 * 1 <= k <= n!
 * <p>
 * 来源：力扣（LeetCode-60）
 * 链接：https://leetcode-cn.com/problems/permutation-sequence
 *
 * @author godfrey
 * @since 2020-11-04
 */
@DisplayName("排列序列")
public class PermutationSequence extends BaseTest {

    @DisplayName("在下一个排列基础上（会超时）-时间复杂度O(nk)，空间复杂度O(1)")
    @ParameterizedTest
    @CsvSource({"3,3", "4,9", "3,1"})
    void getPermutation(int n, int k) {
        int[] nums = new int[n];
        final int len = nums.length;
        for (int i = 0; i < len; ++i) {
            nums[i] = i + 1;
        }
        boolean flag = false;
        while (k-- > 1) {
            for (int i = len - 1; i > 0; --i) {
                if (nums[i - 1] < nums[i]) {
                    if (i < len - 1) {
                        Arrays.sort(nums, i, len);
                    }
                    for (int j = i; j < len; ++j) {
                        if (nums[j] > nums[i - 1]) {
                            int temp = nums[j];
                            nums[j] = nums[i - 1];
                            nums[i - 1] = temp;
                            flag = true;
                            break;
                        }
                    }
                }
                if (flag) {
                    flag = false;
                    break;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int num : nums) {
            sb.append(num);
        }
        System.out.println(sb.toString());
    }

    @DisplayName("康托编码-时间复杂度O(n)，空间复杂度O(1)")
    @ParameterizedTest
    @CsvSource({"3,3", "4,9", "3,1"})
    void getPermutation2(int n, int k) {
        //TODO:康托编码
    }
}
